

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;light&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="https://cdn.jsdelivr.net/gh/kzwrime/kzwrime.github.io/img/favicon.png">
  <link rel="icon" type="image/png" href="https://tuchuangrrr.oss-cn-shenzhen.aliyuncs.com/img/kunnan.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="霜华">
  <meta name="keywords" content="">
  <title>线性时间排序 - kunzh</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/atelier-lakeside-dark.min.css" />
    
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_pf9vaxs7x7b.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_kmeydafke9r.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
</head>


<body>
  <header style="height: 60vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>kunzh</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/links/">
                <i class="iconfont icon-link-fill"></i>
                友链
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/shuoshuo2/">
                <i class="iconfont icon-speakernotes"></i>
                留言板
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner intro-2" id="background" parallax=true
         style="background: url('https://rainrime.top/img/SloveniaAlps.jpg') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container page-header text-center fade-in-up">
            <span class="h2" id="subtitle">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2020-09-24 22:25" pubdate>
        2020年9月24日 晚上
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      2.2k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      32
       分钟
    </span>
  

  
  
    
      <!-- LeanCloud 统计文章PV -->
      <span id="leancloud-post-views-container" class="post-meta" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="leancloud-post-views"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto" id="post">
            <!-- SEO header -->
            <h1 style="display: none">线性时间排序</h1>
            
            <div class="markdown-body" id="post-body">
              <h1 id="线性时间排序"><a class="markdownIt-Anchor" href="#线性时间排序"></a> 线性时间排序</h1>
<p>由决策树模型知：任何基于比较的排序算法，在最坏情况的下界为O(nlgn)，这一复杂度快速排序，堆排序，归并排序已然达到（快排在平均情况下达到，但由于其能较好利用计算机结构而表现较佳）。能否突破这一复杂度呢？本文阐述几个不基于比较的排序算法及他们的C++实现。</p>
<p>开始正文之前，不妨先来看一个有意思的<code>珠排序</code>：</p>
<blockquote>
<p>问题描述：对 [2, 5, 3, 4] 排序</p>
</blockquote>
<ul>
<li>注：想象算盘，<code>[0]</code>是一个珠子，<code>|</code>是串珠子的杆子。</li>
</ul>
<ol>
<li>
<p>将珠子悬挂在竖杆上</p>
<pre><code class="hljs gherkin">[0] [0]  |<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">    // 2</span>
<span class="hljs-string"> </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|
[0] [0] [0] [0] [0]   // 5
 |<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|
[0] [0] [0]  |<span class="hljs-string">   </span>|<span class="hljs-string">    // 3</span>
<span class="hljs-string"> </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|
[0] [0] [0] [0]  |<span class="hljs-string">    // 4</span>
<span class="hljs-string"> </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|
------------------</code></pre>
</li>
<li>
<p>让珠子掉落</p>
<pre><code class="hljs gherkin">[0] [0]  |<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">    // 2</span>
<span class="hljs-string"> </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|
[0] [0] [0]  |<span class="hljs-string">   </span>|<span class="hljs-string">    // 3</span>
<span class="hljs-string"> </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|
[0] [0] [0] [0]  |<span class="hljs-string">    // 4</span>
<span class="hljs-string"> </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|
[0] [0] [0] [0] [0]   // 5
 |<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|<span class="hljs-string">   </span>|
------------------</code></pre>
</li>
</ol>
<p>复杂度分析：</p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span> : 所有珠子同时移动，无法实现</li>
<li><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msqrt><mi>n</mi></msqrt><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\sqrt{n})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.05028em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.8002800000000001em;"><span class="svg-align" style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord" style="padding-left:0.833em;"><span class="mord mathdefault">n</span></span></span><span style="top:-2.76028em;"><span class="pstrut" style="height:3em;"></span><span class="hide-tail" style="min-width:0.853em;height:1.08em;"><svg width='400em' height='1.08em' viewBox='0 0 400000 1080' preserveAspectRatio='xMinYMin slice'><path d='M95,702c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,
-10,-9.5,-14c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54c44.2,-33.3,65.8,
-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10s173,378,173,378c0.7,0,
35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429c69,-144,104.5,-217.7,106.5,
-221c5.3,-9.3,12,-14,20,-14H400000v40H845.2724s-225.272,467,-225.272,467
s-235,486,-235,486c-2.7,4.7,-9,7,-19,7c-6,0,-10,-1,-12,-3s-194,-422,-194,-422
s-65,47,-65,47z M834 80H400000v40H845z'/></svg></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.23972em;"><span></span></span></span></span></span><span class="mclose">)</span></span></span></span> : 重力实现，由<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>h</mi><mo>=</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><mi>g</mi><msup><mi>t</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">h=\frac{1}{2}gt^2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault">h</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.190108em;vertical-align:-0.345em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.845108em;"><span style="top:-2.6550000000000002em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.394em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.345em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mord mathdefault" style="margin-right:0.03588em;">g</span><span class="mord"><span class="mord mathdefault">t</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span>且最高珠子的高度正比于珠子数目得<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msqrt><mi>n</mi></msqrt><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\sqrt{n})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.05028em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.8002800000000001em;"><span class="svg-align" style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord" style="padding-left:0.833em;"><span class="mord mathdefault">n</span></span></span><span style="top:-2.76028em;"><span class="pstrut" style="height:3em;"></span><span class="hide-tail" style="min-width:0.853em;height:1.08em;"><svg width='400em' height='1.08em' viewBox='0 0 400000 1080' preserveAspectRatio='xMinYMin slice'><path d='M95,702c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,
-10,-9.5,-14c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54c44.2,-33.3,65.8,
-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10s173,378,173,378c0.7,0,
35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429c69,-144,104.5,-217.7,106.5,
-221c5.3,-9.3,12,-14,20,-14H400000v40H845.2724s-225.272,467,-225.272,467
s-235,486,-235,486c-2.7,4.7,-9,7,-19,7c-6,0,-10,-1,-12,-3s-194,-422,-194,-422
s-65,47,-65,47z M834 80H400000v40H845z'/></svg></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.23972em;"><span></span></span></span></span></span><span class="mclose">)</span></span></span></span>。</li>
<li><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span> : 电路硬件实现。</li>
</ul>
<blockquote>
<p>以下部分暂未全部完成。</p>
</blockquote>
<h2 id="计数排序"><a class="markdownIt-Anchor" href="#计数排序"></a> 计数排序</h2>
<h4 id="概述"><a class="markdownIt-Anchor" href="#概述"></a> 概述</h4>
<p>计数排序假设：</p>
<p><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi mathvariant="normal">∀</mi><msub><mi>a</mi><mi>i</mi></msub><mo separator="true">,</mo><mi>i</mi><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo separator="true">,</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo stretchy="false">]</mo><mo separator="true">,</mo><msub><mi>a</mi><mi>i</mi></msub><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo separator="true">,</mo><mi>k</mi><mo stretchy="false">]</mo><mtext> </mtext><mo stretchy="false">(</mo><msub><mi>a</mi><mi>i</mi></msub><mo>∈</mo><mi>N</mi><mo separator="true">,</mo><mi>k</mi><mo>∈</mo><mi>N</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\forall a_i, i\in[0,n-1], a_i\in[0,k] \ (a_i\in N, k\in N)
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord">∀</span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">]</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mclose">]</span><span class="mspace"> </span><span class="mopen">(</span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.10903em;">N</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.10903em;">N</span><span class="mclose">)</span></span></span></span></span></p>
<p>即假设输入都是一个小区间内的整数。</p>
<p>当 <em>k=O(n)</em> 时，时间复杂度为 <em>O(n)</em>。</p>
<h4 id="基本思想"><a class="markdownIt-Anchor" href="#基本思想"></a> 基本思想</h4>
<p>对于每个输入元素 <em>x</em>，确定小于 <em>x</em> 的元素个数 <em>m</em>，则可以把 <em>x</em> 放到第 <em>m</em> 个位置上(由0开始计数)，依次排列输出即可。</p>
<p>由于一个元素的输出位置(基本)取决于其值，可以认为，这是一种形式的哈希映射。</p>
<h4 id="整型计数排序的-c-实现"><a class="markdownIt-Anchor" href="#整型计数排序的-c-实现"></a> 整型计数排序的 C++ 实现</h4>
<pre><code class="hljs c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-function"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; <span class="hljs-title">counting_sort</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; arr)</span></span>&#123;
    <span class="hljs-comment">/* arr[i] in [0, maxN] */</span>
    <span class="hljs-keyword">int</span> maxN = <span class="hljs-number">-1</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> &amp;n : arr)
        maxN = n &gt; maxN ? n : maxN;

    <span class="hljs-function"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; <span class="hljs-title">tmp</span><span class="hljs-params">(maxN + <span class="hljs-number">1</span>, <span class="hljs-number">0</span>)</span></span>;
    <span class="hljs-function"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; <span class="hljs-title">ans</span><span class="hljs-params">(arr.size())</span></span>;
    <span class="hljs-comment">/* make tmp[i] contain the number of elements = i */</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> &amp;n : arr)
        tmp[n]++;
    <span class="hljs-comment">/* make tmp[i] contain the number of elements &lt;= i */</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;= maxN; i++)
        tmp[i] += tmp[i - <span class="hljs-number">1</span>];
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = arr.size() - <span class="hljs-number">1</span>; i &gt;= <span class="hljs-number">0</span>; i--)
        ans[--tmp[arr[i]]] = arr[i];
    <span class="hljs-keyword">return</span> ans;
&#125;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; test = &#123;<span class="hljs-number">7</span>, <span class="hljs-number">4</span>, <span class="hljs-number">5</span>, <span class="hljs-number">2</span>, <span class="hljs-number">4</span>, <span class="hljs-number">1</span>, <span class="hljs-number">1</span>, <span class="hljs-number">3</span>, <span class="hljs-number">3</span>, <span class="hljs-number">10</span>, <span class="hljs-number">3</span>&#125;;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; ans = counting_sort(test);
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> n : ans)
        <span class="hljs-built_in">cout</span> &lt;&lt; n &lt;&lt; <span class="hljs-string">&quot; &quot;</span>;
    <span class="hljs-built_in">cout</span> &lt;&lt; <span class="hljs-built_in">endl</span>;
&#125;</code></pre>
<h4 id="过程模拟"><a class="markdownIt-Anchor" href="#过程模拟"></a> 过程模拟：</h4>
<pre><code class="hljs angelscript">arr : i : <span class="hljs-number">0</span> <span class="hljs-number">1</span> <span class="hljs-number">2</span> <span class="hljs-number">3</span> <span class="hljs-number">4</span> <span class="hljs-number">5</span> <span class="hljs-number">6</span> <span class="hljs-number">7</span>
          <span class="hljs-number">2</span> <span class="hljs-number">5</span> <span class="hljs-number">3</span> <span class="hljs-number">0</span> <span class="hljs-number">2</span> <span class="hljs-number">3</span> <span class="hljs-number">0</span> <span class="hljs-number">3</span>
tmp : i : <span class="hljs-number">0</span> <span class="hljs-number">1</span> <span class="hljs-number">2</span> <span class="hljs-number">3</span> <span class="hljs-number">4</span> <span class="hljs-number">5</span>
          <span class="hljs-number">2</span> <span class="hljs-number">0</span> <span class="hljs-number">2</span> <span class="hljs-number">3</span> <span class="hljs-number">0</span> <span class="hljs-number">1</span>
      =&gt;  <span class="hljs-number">2</span> <span class="hljs-number">2</span> <span class="hljs-number">4</span> <span class="hljs-number">7</span> <span class="hljs-number">7</span> <span class="hljs-number">8</span>
      
ans : i : <span class="hljs-number">0</span> <span class="hljs-number">1</span> <span class="hljs-number">2</span> <span class="hljs-number">3</span> <span class="hljs-number">4</span> <span class="hljs-number">5</span> <span class="hljs-number">6</span> <span class="hljs-number">7</span>	
                      <span class="hljs-number">3</span>  	i=<span class="hljs-number">7</span> arr[i]=<span class="hljs-number">3</span> tmp[<span class="hljs-number">3</span>]=<span class="hljs-number">7</span> --tmp[<span class="hljs-number">3</span>]=<span class="hljs-number">6</span>
            <span class="hljs-number">0</span>         <span class="hljs-number">3</span>		i=<span class="hljs-number">6</span> arr[i]=<span class="hljs-number">0</span> tmp[<span class="hljs-number">0</span>]=<span class="hljs-number">2</span> --tmp[<span class="hljs-number">0</span>]=<span class="hljs-number">1</span>
            <span class="hljs-number">0</span>       <span class="hljs-number">3</span> <span class="hljs-number">3</span>		i=<span class="hljs-number">5</span> arr[i]=<span class="hljs-number">3</span> tmp[<span class="hljs-number">3</span>]=<span class="hljs-number">6</span> --tmp[<span class="hljs-number">3</span>]=<span class="hljs-number">5</span>
            <span class="hljs-number">0</span>   <span class="hljs-number">2</span>   <span class="hljs-number">3</span> <span class="hljs-number">3</span>		i=<span class="hljs-number">4</span> arr[i]=<span class="hljs-number">2</span> tmp[<span class="hljs-number">2</span>]=<span class="hljs-number">4</span> --tmp[<span class="hljs-number">2</span>]=<span class="hljs-number">3</span>
          ...............
          <span class="hljs-number">0</span> <span class="hljs-number">0</span> <span class="hljs-number">2</span> <span class="hljs-number">2</span> <span class="hljs-number">3</span> <span class="hljs-number">3</span> <span class="hljs-number">3</span> <span class="hljs-number">5</span></code></pre>
<h4 id="复杂度分析"><a class="markdownIt-Anchor" href="#复杂度分析"></a> 复杂度分析</h4>
<ul>
<li>不考虑找到最大值的过程</li>
<li>遍历 <em>arr</em> 来初始化 <em>tmp</em> 耗时为 <em>Θ(n)</em></li>
<li>再遍历 <em>tmp</em> 耗时为 <em>Θ(k)</em></li>
<li>得到 <em>ans</em> 耗时为 <em>Θ(n)</em></li>
<li>总的时间代价为 <em>Θ(k+n)</em></li>
<li>实际问题中，<em>k=O(n)</em> 时，便一般采用计数排序，此时运行时间为 <em>Θ(n)</em></li>
</ul>
<h4 id="其他"><a class="markdownIt-Anchor" href="#其他"></a> 其他</h4>
<p>计数排序是稳定的。</p>
<h2 id="基数排序"><a class="markdownIt-Anchor" href="#基数排序"></a> 基数排序</h2>
<h4 id="简述"><a class="markdownIt-Anchor" href="#简述"></a> 简述</h4>
<p>基数排序原为应用于卡片排序机上的算法，排序时从某一位开始依次排序。以十进制数为例，每次排序对一位进行排序，使用稳定的排序算法(如计数排序)，排序效果如下(排序过程从左往右):</p>
<table>
<thead>
<tr>
<th>原始</th>
<th>按第三位排序</th>
<th>按第二位排序</th>
<th>按第一位排序</th>
</tr>
</thead>
<tbody>
<tr>
<td>329</td>
<td>72<strong>0</strong></td>
<td>7<strong>2</strong>0</td>
<td><strong>3</strong>29</td>
</tr>
<tr>
<td>457</td>
<td>35<strong>5</strong></td>
<td>3<strong>2</strong>9</td>
<td><strong>3</strong>55</td>
</tr>
<tr>
<td>657</td>
<td>43<strong>6</strong></td>
<td>4<strong>3</strong>6</td>
<td><strong>4</strong>36</td>
</tr>
<tr>
<td>839</td>
<td>45<strong>7</strong></td>
<td>8<strong>3</strong>9</td>
<td><strong>4</strong>57</td>
</tr>
<tr>
<td>436</td>
<td>65<strong>7</strong></td>
<td>3<strong>5</strong>5</td>
<td><strong>6</strong>57</td>
</tr>
<tr>
<td>720</td>
<td>32<strong>9</strong></td>
<td>4<strong>5</strong>7</td>
<td><strong>7</strong>20</td>
</tr>
<tr>
<td>355</td>
<td>83<strong>9</strong></td>
<td>6<strong>5</strong>7</td>
<td><strong>8</strong>39</td>
</tr>
</tbody>
</table>
<p>单纯的数字排序较少使用基数排序，一个典型的应用场景是，在表格中，对多个关键字进行排序。本文以字符串排序为实现。</p>
<h4 id="低位优先的字符串排序lsd"><a class="markdownIt-Anchor" href="#低位优先的字符串排序lsd"></a> 低位优先的字符串排序（LSD）</h4>
<p>这是一个典型应用于定长数据的排序，如账号ID、车牌号等。</p>
<h5 id="c-实现"><a class="markdownIt-Anchor" href="#c-实现"></a> C++ 实现</h5>
<pre><code class="hljs c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;string&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;

<span class="hljs-function"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt; <span class="hljs-title">lsd_sort</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt; arr, <span class="hljs-keyword">int</span> w)</span></span>&#123;
    <span class="hljs-keyword">int</span> n = arr.size();
    <span class="hljs-function"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt; <span class="hljs-title">tmp</span><span class="hljs-params">(n)</span></span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = w - <span class="hljs-number">1</span>; i &gt;= <span class="hljs-number">0</span>; i--)
    &#123;
        <span class="hljs-function"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; <span class="hljs-title">count</span><span class="hljs-params">(<span class="hljs-number">257</span>, <span class="hljs-number">0</span>)</span></span>;		<span class="hljs-comment">// 计算出现频率</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-built_in">string</span> &amp;s : arr)
            count[s[i] + <span class="hljs-number">1</span>]++;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">1</span>; j &lt;= <span class="hljs-number">256</span>; j++)	<span class="hljs-comment">// 将频率转换为索引</span>
            count[j] += count[j - <span class="hljs-number">1</span>];
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; n; j++)		<span class="hljs-comment">// 分类</span>
            tmp[count[arr[j][i]]++] = arr[j];
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; n; j++)		<span class="hljs-comment">// 回写</span>
            arr[j] = tmp[j];
    &#125;
    <span class="hljs-keyword">return</span> arr;
&#125;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt; test = &#123;<span class="hljs-string">&quot;4PGC938&quot;</span>, <span class="hljs-string">&quot;2IYE230&quot;</span>, <span class="hljs-string">&quot;3CI0720&quot;</span>, <span class="hljs-string">&quot;1ICK750&quot;</span>, <span class="hljs-string">&quot;10HV845&quot;</span>, <span class="hljs-string">&quot;4JZY524&quot;</span>, <span class="hljs-string">&quot;1ICK752&quot;</span>&#125;;
    test = lsd_sort(test, <span class="hljs-number">7</span>);
    <span class="hljs-keyword">for</span> (<span class="hljs-built_in">string</span> &amp;s : test)
        <span class="hljs-built_in">cout</span> &lt;&lt; s &lt;&lt; <span class="hljs-built_in">endl</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre>
<h5 id="输出"><a class="markdownIt-Anchor" href="#输出"></a> 输出</h5>
<pre><code class="hljs angelscript"><span class="hljs-number">10</span>HV845
<span class="hljs-number">1</span>ICK750
<span class="hljs-number">1</span>ICK752
<span class="hljs-number">2</span>IYE230
<span class="hljs-number">3</span>CI0720
<span class="hljs-number">4</span>JZY524
<span class="hljs-number">4</span>PGC938</code></pre>
<h2 id="桶排序"><a class="markdownIt-Anchor" href="#桶排序"></a> 桶排序</h2>
<h4 id="概述-2"><a class="markdownIt-Anchor" href="#概述-2"></a> 概述</h4>
<p>桶排序(bucket sort)假设输入数据服从均匀分布(随机)，其平均时间复杂度为 <em>O(n)</em>。</p>
<h4 id="基本思想-2"><a class="markdownIt-Anchor" href="#基本思想-2"></a> 基本思想</h4>
<p>不妨假设输入数据均匀、独立地分布在 [0,1] 区间上，将 [0,1] 均匀地划分为 <em>n</em> 个相同大小的子区间，称为桶。为了得到输出结果，对每个桶中的数据进行排序，然后依次遍历每个桶输出。</p>
<h4 id="01浮点型基数排序的-c-实现"><a class="markdownIt-Anchor" href="#01浮点型基数排序的-c-实现"></a> [0,1）浮点型基数排序的 C++ 实现</h4>
<pre><code class="hljs c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;

<span class="hljs-function"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">double</span>&gt; <span class="hljs-title">bucket_sort</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">double</span>&gt; arr)</span></span>&#123;
    <span class="hljs-keyword">int</span> n = arr.size();
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">double</span>&gt; ans;
    <span class="hljs-function"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">double</span>&gt;&gt; <span class="hljs-title">buckets</span><span class="hljs-params">(n + <span class="hljs-number">1</span>, <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">double</span>&gt;())</span></span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> v : arr)				<span class="hljs-comment">// 分桶存放</span>
        buckets[(<span class="hljs-keyword">int</span>)(n * v)].push_back(v);
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> &amp;v : buckets)			<span class="hljs-comment">// 每个桶排序</span>
        sort(v.begin(), v.end());   <span class="hljs-comment">// sort 在较小时采用插入排序</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> &amp;v : buckets)			<span class="hljs-comment">// 输出</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> m : v)
            ans.push_back(m);
    <span class="hljs-keyword">return</span> ans;
&#125;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">double</span>&gt; test = 
    &#123;<span class="hljs-number">.78</span>, <span class="hljs-number">.17</span>, <span class="hljs-number">.39</span>, <span class="hljs-number">.26</span>, <span class="hljs-number">.72</span>, <span class="hljs-number">.94</span>, <span class="hljs-number">.21</span>, <span class="hljs-number">.12</span>, <span class="hljs-number">.23</span>, <span class="hljs-number">.68</span>&#125;;
    <span class="hljs-keyword">auto</span> ans = bucket_sort(test);
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> v : ans)
        <span class="hljs-built_in">cout</span> &lt;&lt; v &lt;&lt; <span class="hljs-string">&quot; &quot;</span>;
    <span class="hljs-built_in">cout</span> &lt;&lt; <span class="hljs-built_in">endl</span>;
&#125;</code></pre>
<h4 id="正确性证明"><a class="markdownIt-Anchor" href="#正确性证明"></a> 正确性证明</h4>
<p>不妨假设有两个元素满足<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>A</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo>≤</mo><mi>A</mi><mo stretchy="false">[</mo><mi>j</mi><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">A[i] \le A[j]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">A</span><span class="mopen">[</span><span class="mord mathdefault">i</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">A</span><span class="mopen">[</span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mclose">]</span></span></span></span>，由于<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">⌊</mo><mi>n</mi><mi>A</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo stretchy="false">⌋</mo><mo>≤</mo><mo stretchy="false">⌊</mo><mi>n</mi><mi>A</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo stretchy="false">⌋</mo></mrow><annotation encoding="application/x-tex">\lfloor nA[i] \rfloor \le \lfloor nA[i] \rfloor</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">⌊</span><span class="mord mathdefault">n</span><span class="mord mathdefault">A</span><span class="mopen">[</span><span class="mord mathdefault">i</span><span class="mclose">]</span><span class="mclose">⌋</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">⌊</span><span class="mord mathdefault">n</span><span class="mord mathdefault">A</span><span class="mopen">[</span><span class="mord mathdefault">i</span><span class="mclose">]</span><span class="mclose">⌋</span></span></span></span>，有且仅有两种情况</p>
<ul>
<li>A[i] 处于比 A[j] 所在的桶的前面，桶间的遍历是有序的，故输出中 A[i] 在 A[j] 前面</li>
<li>A[i] 和 A[j] 在同一个桶中，每个桶都经过排序故 A[i] 在 A[j] 前面</li>
</ul>
<p>故桶排序是正确的</p>
<h4 id="高位优先的字符串排序msd"><a class="markdownIt-Anchor" href="#高位优先的字符串排序msd"></a> 高位优先的字符串排序（MSD）</h4>
<p><code>LSD</code>的一个显著缺点是不利于处理变长字符串，解决这个问题的一个思路是从高位向地位遍历，先利用键索引计数法将所有字符串按照首字符分到不同桶中，然后依次以同样的方法再对每个桶分割，在当前桶较小时切换为插入排序。</p>
<h5 id="c-实现-2"><a class="markdownIt-Anchor" href="#c-实现-2"></a> C++ 实现</h5>
<pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;string&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;

<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> swift_size = <span class="hljs-number">2</span>;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> R = <span class="hljs-number">256</span>;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">char</span> <span class="hljs-title">get_char</span><span class="hljs-params">(<span class="hljs-built_in">string</span> &amp;s, <span class="hljs-keyword">int</span> index)</span></span>&#123;
    <span class="hljs-keyword">return</span> index &lt; s.size() ? s[index] : <span class="hljs-number">-1</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">msd_sort</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt; &amp;arr, <span class="hljs-keyword">int</span> lo, <span class="hljs-keyword">int</span> hi, <span class="hljs-keyword">int</span> d)</span></span>&#123;
    <span class="hljs-keyword">if</span> (hi &lt;= lo)
        <span class="hljs-keyword">return</span>;
    <span class="hljs-comment">// 以第d个字符为键将a[lo]至a[hi]排序</span>
    <span class="hljs-keyword">if</span> (hi &lt;= lo + swift_size)    &#123;
        sort(arr.begin() + lo, arr.begin() + hi + <span class="hljs-number">1</span>); <span class="hljs-comment">// 插入排序</span>
        <span class="hljs-keyword">return</span>;
    &#125;
    <span class="hljs-function"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; <span class="hljs-title">count</span><span class="hljs-params">(R + <span class="hljs-number">2</span>)</span></span>; 		<span class="hljs-comment">// 计算频率</span>
    <span class="hljs-function"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt; <span class="hljs-title">tmp</span><span class="hljs-params">(arr.size())</span></span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = lo; i &lt;= hi; i++)
        count[arr[i][d] + <span class="hljs-number">2</span>]++;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> r = <span class="hljs-number">0</span>; r &lt; R + <span class="hljs-number">1</span>; r++) <span class="hljs-comment">// 将频率转换为索引</span>
        count[r + <span class="hljs-number">1</span>] += count[r];
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = lo; i &lt;= hi; i++) <span class="hljs-comment">// 数据分类</span>
        tmp[count[arr[i][d] + <span class="hljs-number">1</span>]++] = arr[i];
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = lo; i &lt;= hi; i++) <span class="hljs-comment">// 回写</span>
        arr[i] = tmp[i - lo];

    <span class="hljs-comment">// 递归地以每个字符为键进行排序</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> r = <span class="hljs-number">0</span>; r &lt; R; r++)
        msd_sort(arr, lo + count[r], lo + count[r + <span class="hljs-number">1</span>] - <span class="hljs-number">1</span>, d + <span class="hljs-number">1</span>);
&#125;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>
<span class="hljs-function"></span>&#123;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt; test = &#123; <span class="hljs-string">&quot;she&quot;</span>,<span class="hljs-string">&quot;sells&quot;</span>,<span class="hljs-string">&quot;seashells&quot;</span>,<span class="hljs-string">&quot;by&quot;</span>,<span class="hljs-string">&quot;the&quot;</span>,<span class="hljs-string">&quot;sea&quot;</span>,
                            <span class="hljs-string">&quot;shore&quot;</span>,<span class="hljs-string">&quot;the&quot;</span>,<span class="hljs-string">&quot;shells&quot;</span>,<span class="hljs-string">&quot;she&quot;</span>,<span class="hljs-string">&quot;sells&quot;</span>,<span class="hljs-string">&quot;are&quot;</span>,
                            <span class="hljs-string">&quot;surely&quot;</span>,<span class="hljs-string">&quot;surely&quot;</span>,<span class="hljs-string">&quot;seashells&quot;</span>&#125;;
    msd_sort(test, <span class="hljs-number">0</span>, test.size() - <span class="hljs-number">1</span>, <span class="hljs-number">0</span>);
    <span class="hljs-keyword">for</span> (<span class="hljs-built_in">string</span> &amp;s : test)
        <span class="hljs-built_in">cout</span> &lt;&lt; s &lt;&lt; <span class="hljs-built_in">endl</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre>
<h5 id="输出-2"><a class="markdownIt-Anchor" href="#输出-2"></a> 输出</h5>
<pre><code class="hljs mipsasm">are
<span class="hljs-keyword">by</span>
<span class="hljs-keyword">sea</span>
<span class="hljs-keyword">seashells</span>
<span class="hljs-keyword">seashells</span>
<span class="hljs-keyword">sells</span>
<span class="hljs-keyword">sells</span>
<span class="hljs-keyword">she</span>
<span class="hljs-keyword">she</span>
<span class="hljs-keyword">shells</span>
<span class="hljs-keyword">shore</span>
<span class="hljs-keyword">surely</span>
<span class="hljs-keyword">surely</span>
<span class="hljs-keyword">the</span>
<span class="hljs-keyword">the</span></code></pre>
<h5 id="问题与改进"><a class="markdownIt-Anchor" href="#问题与改进"></a> 问题与改进</h5>
<p>代码中显而易见的一个问题是，256个字母中实际只用了一部分，count大部分无用。如果遇到更大的字母表如<code>unicode</code>空间浪费将极其严重。如<code>Java</code>可以使用<code>TreeSet</code>避免这种情况.</p>
<h2 id="其他-2"><a class="markdownIt-Anchor" href="#其他-2"></a> 其他</h2>
<h3 id="三向字符串快速排序"><a class="markdownIt-Anchor" href="#三向字符串快速排序"></a> 三向字符串快速排序</h3>

            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/%E7%AE%97%E6%B3%95/">算法</a>
                    
                      <a class="hover-with-bg" href="/tags/c/">c++</a>
                    
                      <a class="hover-with-bg" href="/tags/%E6%8E%92%E5%BA%8F/">排序</a>
                    
                  </div>
                
              </div>
              
              
                <div class="post-prevnext row">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2020/10/gdb-stack/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">gdb 调试——栈</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2020/09/%E6%90%9C%E7%B4%A2%E6%8A%80%E6%9C%AF/">
                        <span class="hidden-mobile">几个搜索技术</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
              <!-- Comments -->
              <article class="comments" id="comments">
                
                
  <div id="vcomments"></div>
  <script type="text/javascript">
    function loadValine() {
      addScript('https://cdn.staticfile.org/valine/1.4.14/Valine.min.js', function () {
        new Valine({
          el: "#vcomments",
          app_id: "iAgkjaR2s2ws1XXtS5sVxE7H-MdYXbMMI",
          app_key: "vKka6XRlblVTkbKz8jLXx6EQ",
          placeholder: "你是来自评论区的小惊喜吗 ...",
          path: window.location.pathname,
          avatar: "retro",
          meta: ["nick","mail"],
          pageSize: "10",
          lang: "zh-CN",
          highlight: false,
          recordIP: true,
          serverURLs: "",
        });
      });
    }
    waitElementVisible('vcomments', loadValine);
  </script>
  <noscript>Please enable JavaScript to view the <a target="_blank" href="https://valine.js.org" rel="nofollow noopener noopener">comments
      powered by Valine.</a></noscript>


<!-- 
  <div id="vcomments"></div>
  <script type="text/javascript">
    function loadValine() {
      addScript('https://cdn.staticfile.org/valine/1.4.14/Valine.min.js', function () {
        new Valine({
          el: "#vcomments",
          enableQQ: true,
          boolean: true,
          app_id: "iAgkjaR2s2ws1XXtS5sVxE7H-MdYXbMMI",
          app_key: "vKka6XRlblVTkbKz8jLXx6EQ",
          placeholder: "你是来自评论区的小惊喜吗 ...",
          path: "window.location.pathname",
          avatar: "retro",
          meta: "["nick","mail"]",
          pageSize: "10",
          lang: "zh-CN",
          highlight: false,
          recordIP: true,
          serverURLs: "",
            // 设置Bilibili表情包地址
            emojiCDN: '//i0.hdslb.com/bfs/emote/', 
            // 表情title和图片映射
            emojiMaps: {
            "tv_doge": "6ea59c827c414b4a2955fe79e0f6fd3dcd515e24.png",
            "tv_亲亲": "a8111ad55953ef5e3be3327ef94eb4a39d535d06.png",
            "tv_偷笑": "bb690d4107620f1c15cff29509db529a73aee261.png",
            "tv_再见": "180129b8ea851044ce71caf55cc8ce44bd4a4fc8.png",
            "tv_冷漠": "b9cbc755c2b3ee43be07ca13de84e5b699a3f101.png",
            "tv_发怒": "34ba3cd204d5b05fec70ce08fa9fa0dd612409ff.png",
            "tv_发财": "34db290afd2963723c6eb3c4560667db7253a21a.png",
            "tv_可爱": "9e55fd9b500ac4b96613539f1ce2f9499e314ed9.png",
            "tv_吐血": "09dd16a7aa59b77baa1155d47484409624470c77.png",
            "tv_呆": "fe1179ebaa191569b0d31cecafe7a2cd1c951c9d.png",
            "tv_呕吐": "9f996894a39e282ccf5e66856af49483f81870f3.png",
            "tv_困": "241ee304e44c0af029adceb294399391e4737ef2.png",
            "tv_坏笑": "1f0b87f731a671079842116e0991c91c2c88645a.png",
            "tv_大佬": "093c1e2c490161aca397afc45573c877cdead616.png",
            "tv_大哭": "23269aeb35f99daee28dda129676f6e9ea87934f.png",
            "tv_委屈": "d04dba7b5465779e9755d2ab6f0a897b9b33bb77.png",
            "tv_害羞": "a37683fb5642fa3ddfc7f4e5525fd13e42a2bdb1.png",
            "tv_尴尬": "7cfa62dafc59798a3d3fb262d421eeeff166cfa4.png",
            "tv_微笑": "70dc5c7b56f93eb61bddba11e28fb1d18fddcd4c.png",
            "tv_思考": "90cf159733e558137ed20aa04d09964436f618a1.png",
            "tv_惊吓": "0d15c7e2ee58e935adc6a7193ee042388adc22af.png",
            "tv_打脸": "56ab10b624063e966bfcb76ea5dc4794d87dfd47.png",
            "tv_抓狂": "fe31c08edad661d63762b04e17b8d5ae3c71a757.png",
            "tv_抠鼻": "c666f55e88d471e51bbd9fab9bb308110824a6eb.png",
            "tv_斜眼笑": "911f987aa8bc1bee12d52aafe62bc41ef4474e6c.png",
            "tv_无奈": "ea8ed89ee9878f2fece2dda0ea8a5dbfe21b5751.png",
            "tv_晕": "5443c22b4d07fb1907ccc610c8e6db254f2461b7.png",
            "tv_流汗": "cead1c351ab8d79e9f369605beb90148db0fbed3.png",
            "tv_流泪": "7e71cde7858f0cd50d74b0264aa26db612a8a167.png",
            "tv_流鼻血": "c32d39db2737f89b904ca32700d140a9241b0767.png",
            "tv_点赞": "f85c354995bd99e28fc76c869bfe42ba6438eff4.png",
            "tv_生气": "26702dcafdab5e8225b43ffd23c94ac1ff932654.png",
            "tv_生病": "8b0ec90e6b86771092a498c54f09fc94621c1900.png",
            "tv_疑问": "0793d949b18d7be716078349c202c15ff166f314.png",
            "tv_白眼": "c1d59f439e379ee50eef488bcb5e5378e5044ea4.png",
            "tv_皱眉": "72ccad6679fea0d14cce648b4d818e09b8ffea2d.png",
            "tv_目瞪口呆": "0b8cb81a68de5d5365212c99375e7ace3e7891b7.png",
            "tv_睡着": "8b196675b53af58264f383c50ad0945048290b33.png",
            "tv_笑哭": "1abc628f6d4f4caf9d0e7800878f4697abbc8273.png",
            "tv_腼腆": "89712c0d4af73e67f89e35cbc518420380a7f6f4.png",
            "tv_色": "61822c7e9aae5da76475e7892534545336b23a6f.png",
            "tv_调侃": "4bc022533ef31544ca0d72c12c808cf4a1cce3e3.png",
            "tv_调皮": "b9c41de8e82dd7a8515ae5e3cb63e898bf245186.png",
            "tv_鄙视": "6e72339f346a692a495b123174b49e4e8e781303.png",
            "tv_闭嘴": "c9e990da7f6e93975e25fd8b70e2e290aa4086ef.png",
            "tv_难过": "87f46748d3f142ebc6586ff58860d0e2fc8263ba.png",
            "tv_馋": "fc7e829b845c43c623c8b490ee3602b7f0e76a31.png",
            "tv_鬼脸": "0ffbbddf8a94d124ca2f54b360bbc04feb6bbfea.png",
            "tv_黑人问号": "45821a01f51bc867da9edbaa2e070410819a95b2.png",
            "tv_鼓掌": "1d21793f96ef4e6f48b23e53e3b9e42da833a0f6.png"
                // ... 更多表情
            }
        });
      });
    }
    createObserver(loadValine, 'vcomments');
  </script>
      <style>
        #vcomments textarea {
            box-sizing: border-box;
            background: url("/img/v2-f3d5c26e7ac0da80ee72b6dc178d6aa1_b005.gif") 100% 100% no-repeat;
        }
      </style>
  <noscript>Please enable JavaScript to view the <a target="_blank" href="https://valine.js.org" rel="nofollow noopener noopener">comments
      powered by Valine.</a></noscript>
 -->

              </article>
            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->

  <div class="col-lg-7 mx-auto nopadding-md">
    <div class="container custom post-content mx-auto">
      <img src="/img/371905140-ROBOT-WAVING-400px-unscreen(1).gif" srcset="/img/loading.gif" class="rounded mx-auto d-block mt-5" style="width:200px; height:200px;" >
    </div>
  </div>


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
        <br>
        <span>©2019 - 2020 By</span>
        <a href="https://github.com/rainrime" target="_blank" rel="nofollow noopener"><span>kunzh</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


    

    
  </div>
</footer>


<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/lazyload.js" ></script>
  



  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: '#post-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 6,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "线性时间排序&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
      icon: "❡"
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- KaTeX -->
    <link  rel="stylesheet" href="https://cdn.staticfile.org/KaTeX/0.11.1/katex.min.css" />
  



  
  
    <script type="text/javascript">
      //定义获取词语下标
      var a_idx = 0;
      jQuery(document).ready(function ($) {
        //点击body时触发事件
        $("body").click(function (e) {
          //需要显示的词语
          var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正", "法治", "爱国", "敬业", "诚信", "友善");
          //设置词语给span标签
          var $i = $("<span/>").text(a[a_idx]);
          //下标等于原来下标+1  余 词语总数
          a_idx = (a_idx + 1) % a.length;
          //获取鼠标指针的位置，分别相对于文档的左和右边缘。
          //获取x和y的指针坐标
          var x = e.pageX, y = e.pageY;
          //在鼠标的指针的位置给$i定义的span标签添加css样式
          $i.css({
            "z-index": 999,
            "top": y - 20,
            "left": x,
            "position": "absolute",
            "font-weight": "bold",
            "color": rand_color()
          });
          // 随机颜色
          function rand_color() {
            return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
          }
          //在body添加这个标签
          $("body").append($i);
          //animate() 方法执行 CSS 属性集的自定义动画。
          //该方法通过CSS样式将元素从一个状态改变为另一个状态。CSS属性值是逐渐改变的，这样就可以创建动画效果。
          //详情请看http://www.w3school.com.cn/jquery/effect_animate.asp
          $i.animate({
            //将原来的位置向上移动180
            "top": y - 180,
            "opacity": 0
            //1500动画的速度
          }, 1500, function () {
            //时间到了自动删除
            $i.remove();
          });
        });
      })
      ;
    </script>
  



  <script>(function (i, s, o, g, r, a, m) {
      i['DaoVoiceObject'] = r;
      i[r] = i[r] ||
        function () {
          (i[r].q = i[r].q || []).push(arguments);
        };
      i[r].l = 1 * new Date();
      a = s.createElement(o);
      m = s.getElementsByTagName(o)[0];
      a.async = 1;
      a.src = g;
      a.charset = 'utf-8';
      m.parentNode.insertBefore(a, m);
    })(window, document, 'script', ('https:' === document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/244aa65c.js", 'daovoice');
    daovoice('init', {
      app_id: "244aa65c",
    });
    daovoice('update');
  </script>









  

  

  

  

  

  





</body>
</html>
